{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Brace Expansion II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #breadth-first-search #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #广度优先搜索 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: braceExpansionII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #花括号展开 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果你熟悉 Shell 编程，那么一定了解过花括号展开，它可以用来生成任意字符串。</p>\n",
    "\n",
    "<p>花括号展开的表达式可以看作一个由 <strong>花括号</strong>、<strong>逗号</strong> 和 <strong>小写英文字母</strong> 组成的字符串，定义下面几条语法规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果只给出单一的元素&nbsp;<code>x</code>，那么表达式表示的字符串就只有&nbsp;<code>\"x\"</code>。<code>R(x) = {x}</code>\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>例如，表达式 <code>\"a\"</code> 表示字符串 <code>\"a\"</code>。</li>\n",
    "\t\t<li>而表达式 <code>\"w\"</code> 就表示字符串 <code>\"w\"</code>。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>当两个或多个表达式并列，以逗号分隔，我们取这些表达式中元素的并集。<code>R({e_1,e_2,...}) = R(e_1)&nbsp;∪ R(e_2)&nbsp;∪ ...</code>\n",
    "\t<ul>\n",
    "\t\t<li>例如，表达式 <code>\"{a,b,c}\"</code> 表示字符串&nbsp;<code>\"a\",\"b\",\"c\"</code>。</li>\n",
    "\t\t<li>而表达式 <code>\"{{a,b},{b,c}}\"</code> 也可以表示字符串&nbsp;<code>\"a\",\"b\",\"c\"</code>。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>要是两个或多个表达式相接，中间没有隔开时，我们从这些表达式中各取一个元素依次连接形成字符串。<code>R(e_1 + e_2) = {a + b for (a, b) in&nbsp;R(e_1)&nbsp;× R(e_2)}</code>\n",
    "\t<ul>\n",
    "\t\t<li>例如，表达式 <code>\"{a,b}{c,d}\"</code> 表示字符串&nbsp;<code>\"ac\",\"ad\",\"bc\",\"bd\"</code>。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>表达式之间允许嵌套，单一元素与表达式的连接也是允许的。\n",
    "\t<ul>\n",
    "\t\t<li>例如，表达式 <code>\"a{b,c,d}\"</code> 表示字符串&nbsp;<code>\"ab\",\"ac\",\"ad\"​​​​​​</code>。</li>\n",
    "\t\t<li>例如，表达式 <code>\"a{b,c}{d,e}f{g,h}\"</code> 可以表示字符串&nbsp;<code>\"abdfg\", \"abdfh\", \"abefg\", \"abefh\", \"acdfg\", \"acdfh\", \"acefg\", \"acefh\"</code>。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>给出表示基于给定语法规则的表达式&nbsp;<code>expression</code>，返回它所表示的所有字符串组成的有序列表。</p>\n",
    "\n",
    "<p>假如你希望以「集合」的概念了解此题，也可以通过点击 “<strong>显示英文描述</strong>” 获取详情。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"{a,b}{c,{d,e}}\"\n",
    "<strong>输出：</strong>[\"ac\",\"ad\",\"ae\",\"bc\",\"bd\",\"be\"]</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"{{a,z},a{b,c},{ab,z}}\"\n",
    "<strong>输出：</strong>[\"a\",\"ab\",\"ac\",\"z\"]\n",
    "<strong>解释：</strong>输出中 <strong>不应 </strong>出现重复的组合结果。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= expression.length &lt;= 60</code></li>\n",
    "\t<li><code>expression[i]</code> 由 <code>'{'</code>，<code>'}'</code>，<code>','</code>&nbsp;或小写英文字母组成</li>\n",
    "\t<li>给出的表达式&nbsp;<code>expression</code>&nbsp;用以表示一组基于题目描述中语法构造的字符串</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [brace-expansion-ii](https://leetcode.cn/problems/brace-expansion-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [brace-expansion-ii](https://leetcode.cn/problems/brace-expansion-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"{a,b}{c,{d,e}}\"', '\"{{a,z},a{b,c},{ab,z}}\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, expression: str) -> List[str]:\n",
    "        def calc(ops, exps):\n",
    "            e1 = exps.pop()\n",
    "            e2 = exps.pop()\n",
    "            op = ops.pop()\n",
    "            if op == '+':\n",
    "                exps.append(e1 + e2)\n",
    "            elif op == '*':\n",
    "                # print(f'{op, ops, exps}')\n",
    "                tmp = [b + a for a in e1 for b in e2] \n",
    "                exps.append(tmp)\n",
    "            # print(f'{ops, exps}')\n",
    "\n",
    "        ops, exps = [], []\n",
    "        s, n = expression, len(expression)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            x = s[i]\n",
    "            # print(f'x={x}, i={i}, {ops, exps}')\n",
    "            if x == '{':\n",
    "                if i and s[i-1] not in \",{\": \n",
    "                    ops.append('*')\n",
    "                ops.append('{')\n",
    "                i += 1 \n",
    "            elif x == '}':\n",
    "                while ops and ops[-1] != '{':\n",
    "                    calc(ops, exps)\n",
    "                ops.pop()\n",
    "                i += 1\n",
    "            elif x.isalpha():\n",
    "                j = i \n",
    "                t = \"\"\n",
    "                while j < n and s[j].isalpha():\n",
    "                    t += s[j]\n",
    "                    j += 1\n",
    "                if i and s[i-1] == '}':\n",
    "                    ops.append('*')\n",
    "                exps.append([t])\n",
    "                i = j\n",
    "            else: #comma\n",
    "                while ops and ops[-1] != '{':\n",
    "                    calc(ops, exps)\n",
    "                ops.append('+')\n",
    "                i += 1\n",
    "        while ops:\n",
    "            calc(ops, exps)\n",
    "        return sorted(set(exps[0]))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, expression: str) -> List[str]:\n",
    "        stack = []\n",
    "        n = len(expression)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if expression[i] == \"{\":\n",
    "                stack.append({\"{\"})\n",
    "                i += 1\n",
    "            elif expression[i] == \",\":\n",
    "                stack.append({\",\"})\n",
    "                i += 1\n",
    "            elif expression[i] == \"}\":\n",
    "                se = set()\n",
    "                while stack and stack[-1] != {\"{\"}:\n",
    "                    for x in stack.pop():\n",
    "                        if x != \",\":\n",
    "                            se.add(x)\n",
    "                stack.pop()\n",
    "                stack.append(se)\n",
    "                i += 1\n",
    "            else:\n",
    "                st = \"\"\n",
    "                while i < n and expression[i].islower():\n",
    "                    st += expression[i]\n",
    "                    i += 1\n",
    "                stack.append({st})\n",
    "            if len(stack) >= 2 and stack[-2] not in [{\",\"}, {\"{\"}] and stack[-1] not in [{\",\"}, {\"{\"}]:\n",
    "                se = stack.pop()\n",
    "                pre = stack.pop()\n",
    "    \n",
    "                nex = set()\n",
    "                for p in pre:\n",
    "                    for q in se:\n",
    "                        nex.add(p+q)\n",
    "                stack.append(nex)\n",
    "                \n",
    "        ans = set()\n",
    "        for ls in stack:\n",
    "            if ls != {\",\"}:\n",
    "                for x in ls:\n",
    "                    ans.add(x)\n",
    "        return sorted(list(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, expression: str) -> List[str]:\n",
    "        def merge(pre, ll):\n",
    "            if not ll:\n",
    "                return pre if isinstance(pre, list) else [pre]\n",
    "            res = []\n",
    "            if isinstance(pre, list):\n",
    "                for p in pre:\n",
    "                    for l in ll:\n",
    "                        res.append(p + l)\n",
    "            else:\n",
    "                for l in ll:\n",
    "                    res.append(pre + l)\n",
    "            return res\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for w in expression:\n",
    "            if not stack:\n",
    "                stack.append(w)\n",
    "            else:\n",
    "                if w in '{,' or w.isalpha():\n",
    "                    stack.append(w)\n",
    "                else:\n",
    "                    node, tmp = [], []\n",
    "                    while stack and stack[-1] != '{':\n",
    "                        if stack[-1] == ',':\n",
    "                            node += tmp\n",
    "                            tmp = []\n",
    "                        else:\n",
    "                            tmp = merge(stack[-1], tmp)\n",
    "                        stack.pop()\n",
    "                    stack.pop()\n",
    "                    stack.append(node + tmp)\n",
    "\n",
    "        for ll in stack[1:]:\n",
    "            stack[0] = merge(stack[0], ll)\n",
    "\n",
    "        return sorted(set(stack[0]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, expression: str) -> List[str]:\n",
    "        def merge(pre, ll):\n",
    "            if not ll:\n",
    "                return pre if isinstance(pre, list) else [pre]\n",
    "            res = []\n",
    "            if isinstance(pre, list):\n",
    "                for p in pre:\n",
    "                    for l in ll:\n",
    "                        res.append(p + l)\n",
    "            else:\n",
    "                for l in ll:\n",
    "                    res.append(pre + l)\n",
    "            return res\n",
    "\n",
    "        stack = []\n",
    "\n",
    "\n",
    "        for w in expression:\n",
    "            print(w , '------------------------------')\n",
    "            if not stack:\n",
    "                stack.append(w)\n",
    "            else:\n",
    "                if w in '{,':\n",
    "                    stack.append(w)\n",
    "                elif w == '}':\n",
    "                    node, s = [], []\n",
    "                    while stack and stack[-1] != '{':\n",
    "                        \n",
    "                        if stack[-1] == ',':\n",
    "                            node += s\n",
    "                            s = []\n",
    "                        else:\n",
    "                            s = merge(stack[-1], s)\n",
    "                        stack.pop()\n",
    "\n",
    "                    stack.pop()\n",
    "\n",
    "                    if s:\n",
    "                        node += s\n",
    "\n",
    "\n",
    "                    stack.append(node) \n",
    "\n",
    "                else:\n",
    "                    stack.append(w)\n",
    "            print(stack)\n",
    "            print('\\n')\n",
    "\n",
    "        print(stack)\n",
    "\n",
    "        for ll in stack[1:]:\n",
    "            stack[0] = merge(stack[0], ll)\n",
    "\n",
    "        return sorted(set(stack[0]))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, expression: str) -> List[str]:\n",
    "        tokens = [x for x in re.split(r'([,{}])', expression) if x != '']\n",
    "\n",
    "        print(tokens)\n",
    "        n = len(tokens)\n",
    "\n",
    "        def expr(i):\n",
    "            print('expr', i, tokens[i])\n",
    "            ret = set()\n",
    "\n",
    "            while True:\n",
    "                j, s = term(i)\n",
    "                print('e', i, j, s)\n",
    "                ret.update(s)\n",
    "                i = j\n",
    "\n",
    "                if i < n and tokens[i] == ',':\n",
    "                    i += 1\n",
    "\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            print(ret)\n",
    "\n",
    "            return i, ret\n",
    "\n",
    "        def term(i):\n",
    "            print('term', i, tokens[i])\n",
    "            ret = {''}\n",
    "\n",
    "            while i < n and (tokens[i] == '{' or tokens[i].isalpha()):\n",
    "                j, s = item(i)\n",
    "                print('t', i, j, s)\n",
    "\n",
    "                tmp = set()\n",
    "                for a in ret:\n",
    "                    for b in s:\n",
    "                        print(a, b)\n",
    "                        tmp.add(a + b)\n",
    "\n",
    "                ret = tmp\n",
    "\n",
    "                i = j\n",
    "\n",
    "            print('t', ret)\n",
    "\n",
    "            return i, ret\n",
    "\n",
    "        def item(i):\n",
    "            print('item', i, tokens[i])\n",
    "            \n",
    "            if tokens[i] == '{':\n",
    "                j, s = expr(i + 1)\n",
    "                return j + 1, s\n",
    "            else:\n",
    "                return i + 1, {tokens[i]}\n",
    "\n",
    "        return list(sorted(list(expr(0)[1])))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, expression: str) -> List[str]:\n",
    "        tokens = [x for x in re.split(r'([,{}])', expression) if x != '']\n",
    "\n",
    "        print(tokens)\n",
    "        n = len(tokens)\n",
    "\n",
    "        def expr(i):\n",
    "            ret = set()\n",
    "\n",
    "            while True:\n",
    "                j, s = term(i)\n",
    "                print('e', i, j, s)\n",
    "                ret.update(s)\n",
    "                i = j\n",
    "\n",
    "                if i < n and tokens[i] == ',':\n",
    "                    i += 1\n",
    "\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            return i, ret\n",
    "\n",
    "        def term(i):\n",
    "            ret = {''}\n",
    "\n",
    "            while i < n and (tokens[i] == '{' or tokens[i].isalpha()):\n",
    "                j, s = item(i)\n",
    "\n",
    "                tmp = set()\n",
    "                for a in ret:\n",
    "                    for b in s:\n",
    "                        print(a, b)\n",
    "                        tmp.add(a + b)\n",
    "\n",
    "                ret = tmp\n",
    "\n",
    "                i = j\n",
    "\n",
    "            return i, ret\n",
    "\n",
    "        def item(i):\n",
    "            if tokens[i] == '{':\n",
    "                j, s = expr(i + 1)\n",
    "                return j + 1, s\n",
    "            else:\n",
    "                return i + 1, {tokens[i]}\n",
    "\n",
    "        return list(sorted(list(expr(0)[1])))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, expression: str) -> List[str]:\n",
    "        def dfs(exp):\n",
    "            j = exp.find('}')\n",
    "            if j == -1:\n",
    "                s.add(exp)\n",
    "                return \n",
    "            i = exp.rfind('{', 0, j - 1)\n",
    "            a, c = exp[:i], exp[j+1:]\n",
    "            for b in exp[i+1: j].split(','):\n",
    "                dfs(a + b + c)\n",
    "        s = set()\n",
    "        dfs(expression)\n",
    "        return sorted(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, e: str) -> List[str]:\n",
    "        v = set()\n",
    "        def dfs(x):\n",
    "            j = x.find('}')\n",
    "            if j==-1:\n",
    "                v.add(x)\n",
    "                return \n",
    "            i = x[:j].rfind('{')\n",
    "            a = x[:i]\n",
    "            c = x[j+1:]\n",
    "            for b in x[i+1:j].split(','):\n",
    "                dfs(a + b + c)\n",
    "        dfs(e)\n",
    "        return sorted(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, expression: str) -> List[str]:\n",
    "        def dfs(s):\n",
    "            i = s.find('}')\n",
    "            if i == -1:\n",
    "                st.add(s)\n",
    "                return\n",
    "            j = s.rfind('{', 0, i - 1)\n",
    "            for x in s[j + 1:i].split(','):\n",
    "                dfs(s[:j] + x + s[i+1:])\n",
    "        st = set()\n",
    "        dfs(expression)\n",
    "        return sorted(st)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, expression: str) -> List[str]:\n",
    "        def dfs(exp):\n",
    "            right_index = exp.find('}')\n",
    "            if right_index == -1:\n",
    "                ans.add(exp)\n",
    "                return\n",
    "            left_index = exp.rfind('{', 0, right_index)\n",
    "            a, c = exp[:left_index], exp[right_index+1:]\n",
    "            for b in exp[left_index+1:right_index].split(','):\n",
    "                dfs(a+b+c)\n",
    "        \n",
    "        ans = set()\n",
    "        dfs(expression)\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def braceExpansionII(self, expression: str) -> List[str]:\n",
    "\n",
    "        def dfs(exp):\n",
    "            j = exp.find('}')\n",
    "            if j == -1:\n",
    "                s.add(exp)\n",
    "                return\n",
    "            i = exp.rfind('{', 0, j - 1)\n",
    "            a, c = exp[:i], exp[j + 1:]\n",
    "            for b in exp[i + 1: j].split(','):\n",
    "                dfs(a + b + c)\n",
    "\n",
    "        s = set()\n",
    "        dfs(expression)\n",
    "        return sorted(s)\n",
    "      "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
